package com.hanxiaozhang.no10leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈 给一棵非空二叉树，找到路径和的最大值。〉
 * <p>
 * 实例1:
 * .    1
 * .   / \
 * .  2   3
 * 输入: [1,2,3]
 * 输出: 6
 * 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
 * 实例2:
 * 输入：root = [-10,9,20,null,null,15,7]
 * .   -10
 * .   / \
 * .  9   20
 * .     /  \
 * .   15    7
 * 输出：42
 * 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
 * <p>
 * 难度：
 * 正确答案不一定是从叶子节点到最顶部的根节点，子树中节点的任意链接，甚至单个节点都有可能是最大值。
 * 思路：
 * 定义一个静态成员变量，在每次计算出最大值的时，进行比较即可。
 * 即，按照递归的方法计算所有可能的路径和，在每一次求出当前路径和的时候都与max值去比较，最后返回max值。
 *
 * @author hanxinghua
 * @create 2024/4/25
 * @since 1.0.0
 */
public class No124BinaryTreeMaxPathSum {

    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(1);
        tree1.left = new TreeNode(2);
        tree1.right = new TreeNode(3);

        TreeNode tree2 = new TreeNode(-10);
        tree2.left = new TreeNode(9);
        tree2.right = new TreeNode(20);
        tree2.right.left = new TreeNode(15);
        tree2.right.right = new TreeNode(7);

        System.out.println(method1(tree1));
        System.out.println(method1(tree2));

    }


    private static int max = Integer.MIN_VALUE;

    /**
     * 方法1
     *
     * @param root
     * @return
     */
    public static int method1(TreeNode root) {
        if (root == null) {
            return 0;
        }

        sumMax(root);
        return max;
    }

    public static int sumMax(TreeNode root) {

        if (root == null) {
            return 0;
        }

        // 左孩子最长
        int left = Math.max(0, sumMax(root.left));
        // 右孩子最长
        int right = Math.max(0, sumMax(root.right));
        // 整体最长
        max = Math.max(max, left + right + root.val);
        // 获取Math.max(左节点最长,右节点最长)，加上当前节点值
        return Math.max(left, right) + root.val;
    }


}
